package com.monday.greedy.algorithm;

import java.util.Arrays;

/**
 *   有 m 个糖果和 n 个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m<n）
 *   所以糖果只能分配给一部分孩子。每个糖果的大小不等，这 m 个糖果的大小分别是 s1，s2，s3，……，sm。
 *   除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小 >= 孩子的对糖果大小的需求的时候，孩子才得到满足。
 *   假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。
 */
public class ShareCandyInSeparable {

    /**
     * 分糖果
     *  1、选择糖果和孩子的需求进行排序
     *  2、从第一个孩子开始，遍历糖果，如果糖果大小 >= 孩子的需求，则分给孩子
     *  3、继续遍历下一个孩子
     *  4、直到所有孩子都分到糖果或者糖果分完
     */
    public void shareCandy(int[] candies, int[] children) {
        // 先对糖果和孩子的需求进行排序
        Arrays.sort(children);
        Arrays.sort(candies);

        System.out.println("孩子需求：" + Arrays.toString(children));
        System.out.println("糖果大小：" + Arrays.toString(candies));
        System.out.println("分配结果====================");

        // 孩子下标
        int i = 0;
        // 糖果下标
        int j = 0;
        while(i < children.length && j < candies.length) {
            // 如果糖果大小 >= 孩子的需求，则分给孩子
            if(candies[j] >= children[i]) {
                System.out.println("孩子需求为:" + children[i] + ",\t得到糖果:" + candies[j]);
                i++;
            }
            j++;
        }
    }

}
